package org.example.day02;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * 一个局域网内有很多台电脑，分别标注为0 - N-1的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。<br> 其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回-1<br> 给定一个数组times表示一个电脑把相邻电脑感染所用的时间。<br> 如图：path[i]= {i,j, t} 表示电脑i-&gt;j 电脑i上的病毒感染j，需要时间t。<br> <br>
 *
 * 一个局域网内有很多台电脑，分别标注为0 - N-1的数字。
 * 相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。
 * 其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。
 * 如果最后有电脑不会感染，则返回-1 给定一个数组times表示一个电脑把相邻电脑感染所用的时间。
 * 如图：path[i]= {i,j, t} 表示电脑i上的病毒感染电脑j，需要时间t。
 * @date 2024/3/11 15:22
 */
public class test027  {
    static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int networkDelayTime(List<int[]> times, int N, int K) {
        // 构建图的邻接表表示
        Map<Integer, List<Edge>> graph = new HashMap<>(); // 使用HashMap来存储邻接表
        for (int i = 1; i <= N; i++) {
            graph.put(i, new ArrayList<>()); // 初始化邻接表
        }

        for (int[] time : times) {
            int u = time[0]; // 边的起点
            int v = time[1]; // 边的终点
            int w = time[2]; // 边的权重
            graph.get(u).add(new Edge(v, w)); // 将边添加到起点的邻接表中
        }

        // 初始化距离数组，所有的距离初始化为无穷大
        // 将起点的距离初始化为0
        Map<Integer, Integer> dist = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            dist.put(i, Integer.MAX_VALUE);
        }
        dist.put(K, 0);

        // 使用堆（优先队列）来得到当前最短的感染时间
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        heap.offer(new int[]{0, K}); // 将起点加入堆中
        while (!heap.isEmpty()) {
            int[] curr = heap.poll(); // 弹出堆顶元素，即当前最短的感染时间和对应的节点
            int time = curr[0]; // 当前的感染时间
            int node = curr[1]; // 当前的节点

            // 如果当前的时间比已知的感染时间大，那么就不用继续处理
            if (time > dist.get(node)) {
                continue;
            }

            for (Edge edge : graph.get(node)) {
                int v = edge.to; // 相邻节点
                int w = edge.weight; // 边的权重

                // 如果通过当前节点感染相邻节点的时间更短，则更新时间
                if (time + w < dist.get(v)) {
                    dist.put(v, time + w);
                    heap.offer(new int[]{dist.get(v), v}); // 将更新后的节点和时间加入堆中
                }
            }
        }

        // 最后检查是否所有电脑都被感染，如果是，返回最大的感染时间
        int maxDist = Collections.max(dist.values());
        return maxDist < Integer.MAX_VALUE ? maxDist : -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 电脑数量
        int connections = scanner.nextInt(); // 连接数量
        List<int[]> times = new ArrayList<>(); // 存储连接信息的列表
        for (int i = 0; i < connections; i++) {
            int u = scanner.nextInt(); // 边的起点
            int v = scanner.nextInt(); // 边的终点
            int w = scanner.nextInt(); // 边的权重
            times.add(new int[]{u, v, w}); // 将连接信息添加到列表中
        }
        int K = scanner.nextInt(); // 起点

        // 计算输出
        System.out.println(networkDelayTime(times, N, K));
        scanner.close();
    }
}
